class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size(), m = board[0].size();

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (f(board, i, j, word, 0))
                    return true;
            }
        }
        return false;
    }

    bool f(vector<vector<char>>& board, int i, int j, string& w, int k)
    {
        if (k == w.size())
            return true;

        if (i < 0 || i == board.size()
            || j < 0 || j == board[0].size() || board[i][j] != w[k])
            return false;

        char tmp = board[i][j];
        board[i][j] = 0;

        bool ans = f(board, i + 1, j, w, k + 1) ||
            f(board, i, j + 1, w, k + 1) ||
            f(board, i - 1, j, w, k + 1) ||
            f(board, i, j - 1, w, k + 1);
        board[i][j] = tmp;

        return ans;
    }
};